// tspcluster - Traveling Salesman Problem
// Copyright (C) 2006  Frederik Carlier
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

using System;
using System.Globalization;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace UGent.Tsp
{
    /// <summary>
    /// Represents a map.
    /// </summary>
    [Serializable()]
    public class Map
    {
        #region Constructor
        public Map()
            : this(Map.DefaultDimension, Map.DefaultCityCount, Map.DefaultMetric, true)
        {
        }

        public Map(int cityCount)
            : this(Map.DefaultDimension, cityCount, Map.DefaultMetric, true)
        {
        }

        public Map(int dimension, int cityCount, Metric metric, bool random)
        {
            if (dimension <= 0)
                throw new ArgumentOutOfRangeException("dimension");

            if (cityCount <= 0)
                throw new ArgumentOutOfRangeException("cityCount");

            this.dimension = dimension;
            this.cityCount = cityCount;
            this.metric = metric;

            coordinates = new double[cityCount, dimension];

            if (random)
            {
                Random generator = new Random();

                // Create random coordinates of the cities
                for (int i = 0; i < cityCount; i++)
                {
                    for (int d = 0; d < dimension; d++)
                    {
                        coordinates[i, d] = generator.NextDouble();
                    }
                }
            }

            CalculateDistances();
        }

        public Map(string filename)
        {
            if (!File.Exists(filename))
                throw new FileNotFoundException();

            if (Path.GetExtension(filename) == ".tsplib")
                using (FileStream stream = new FileStream(filename, FileMode.Open, FileAccess.Read))
                {
                    LoadTspLibMap(stream);
                }
            else
                using (FileStream stream = new FileStream(filename, FileMode.Open, FileAccess.Read))
                {
                    LoadUGentTspMap(stream);
                }
        }

        private void LoadUGentTspMap(Stream stream)
        {
            using (StreamReader reader = new StreamReader(stream))
            {
                // 1. read the distance matrix
                // 2. read the coordinates

                string line = null;
                while (string.IsNullOrEmpty(line))
                    line = reader.ReadLine();

                string[] fileDistances = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);

                this.cityCount = fileDistances.Length;
                distances = new double[cityCount, cityCount];

                for (int i = 0; i < cityCount; i++)
                {
                    if (i != 0)
                    {
                        line = reader.ReadLine();
                        fileDistances = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                    }

                    for (int j = i + 1; j < cityCount; j++)
                    {
                        // Console.WriteLine("Parsing {0}={1}", "fileDistances[" + j + "]", fileDistances[j]);
                        distances[i, j] = double.Parse(fileDistances[j], CultureInfo.InvariantCulture);
                        distances[j, i] = distances[i, j];
                    }

                    line = null;
                }

                while (string.IsNullOrEmpty(line))
                    line = reader.ReadLine();

                dimension = 2;
                coordinates = new double[cityCount, dimension];

                for (int i = 0; i < cityCount; i++)
                {
                    string[] fileCoordinates = line.Split(',');

                    // file contains latitude, longitude
                    // x = longitude
                    // y = 1/2 ln(1+sin long/1-sin long)

                    double latitude = double.Parse(fileCoordinates[0], CultureInfo.InvariantCulture);
                    double longitude = double.Parse(fileCoordinates[1], CultureInfo.InvariantCulture);
                    //Console.WriteLine("After parsing:");
                    //Console.WriteLine("Coordinates: ({0}, {1})", latitude, longitude);

                    latitude = latitude / 360.0 * (2.0 * Math.PI);
                    longitude = longitude / 360.0 * (2.0 * Math.PI);

                    coordinates[i, 0] = longitude;
                    coordinates[i, 1] = 0.5 * (Math.Log(1.0 + Math.Sin(latitude)) - Math.Log(1.0 - Math.Sin(latitude)));

                    //Console.WriteLine("After projecting:");
                    //Console.WriteLine("Coordinates: ({0}, {1})", coordinates[i, 0], coordinates[i, 1]);

                    line = reader.ReadLine();
                }
                
                //for(int i = 0; i < cityCount; i++)
                //{
                //    for(int j = i + 1; j < cityCount; j++)
                //    {
                //        double timeDistance = this.distances[i,j];
                //        double realDistance = Distance.Calculate(Metric.Euclidian, 2, new double[]{coordinates[i,0], coordinates[i,1]}, new double[]{coordinates[j,0], coordinates[j,1]});
                //        Console.WriteLine("Distances {0}-{1} ratio time/distance: {2}", i, j, timeDistance/realDistance);
                //    }
                //}
                
                CalculateDistances();
            }
        }

        private void LoadTspLibMap(Stream stream)
        {
            using (StreamReader reader = new StreamReader(stream))
            {
                while (reader.Peek() >= 0)
                {
                    string line = reader.ReadLine();

                    if (string.IsNullOrEmpty(line))
                        continue;

                    line = CleanInputString(line);
                    string[] parts = line.Split(':');

                    Debug.Assert(parts != null && parts.Length > 0 && parts.Length < 3);

                    string name = parts[0].Trim().ToUpper();
                    string value = parts.Length > 1 ? parts[1].Trim() : null;

                    Console.Write(string.Format("Parsing property '{0}' with value '{1}'...", name, value));

                    switch (name)
                    {
                        case ("NAME"):
                            this.name = value;
                            break;
                        case ("TYPE"):
                            if (value != "TSP")
                                throw new NotSupportedException("Only TSP problems are supported.");
                            break;
                        case ("COMMENT"):
                            this.comment = value;
                            break;
                        case ("DIMENSION"):
                            this.cityCount = Convert.ToInt32(value);
                            break;
                        case ("CAPACITY"):
                            throw new NotSupportedException("The Capacity property is not supported.");
                        case ("EDGE_WEIGHT_TYPE"):
                            switch (value.ToUpper())
                            {
                                case ("EUC_2D"):
                                case ("EUC_3D"):
                                    this.metric = Metric.Euclidian;
                                    break;
                                case ("MAX_2D"):
                                case ("MAX_3D"):
                                    this.metric = Metric.Maximum;
                                    break;
                                case ("MAN_2D"):
                                case ("MAN_3D"):
                                    this.metric = Metric.Manhattan;
                                    break;
                                case ("GEO"):
                                    this.metric = Metric.Geographical;
                                    break;
                                default:
                                    throw new NotSupportedException(string.Format("The value {0} for EDGE_WEIGHT_TYPE is not supported.", value));
                            }

                            if (this.dimension == 0)
                            {
                                Console.WriteLine("Auto-completing the dimension data.");

                                switch (value.ToUpper())
                                {
                                    case ("EUC_2D"):
                                    case ("MAX_2D"):
                                    case ("MAN_2D"):
                                    case ("GEO"):
                                        this.dimension = 2;
                                        break;
                                    case ("EUC_3D"):
                                    case ("MAX_3D"):
                                    case ("MAN_3D"):
                                        this.dimension = 3;
                                        break;
                                    default:
                                        throw new NotSupportedException(string.Format("The value {0} for EDGE_WEIGHT_TYPE is not supported.", value));
                                }
                            }
                            break;
                        case "EDGE_WEIGHT_FORMAT":
                            throw new NotSupportedException("The Edge Weight Format property is not supported.");
                        case "EDGE_DATA_FORMAT":
                        case "NODE_COORD_TYPE":
                        case "DISPLAY_DATA_TYPE":
                            throw new NotSupportedException();
                        case "NODE_COORD_SECTION":
                            Console.WriteLine(string.Format("Reading the nodes data. Dimension: {0}.", dimension));

                            this.coordinates = new double[cityCount, dimension];

                            for (int i = 0; i < cityCount; i++)
                            {
                                line = reader.ReadLine();
                                line = CleanInputString(line);
                                parts = line.Split(' ');

                                Debug.Assert(parts.Length == dimension + 1);

                                int index = Int32.Parse(parts[0]);
                                Debug.Assert(index == i + 1);

                                for (int d = 0; d < dimension; d++)
                                {
                                    this.coordinates[i, d] = Double.Parse(parts[d + 1]);
                                }

#if DEBUG
                                StringBuilder sb = new StringBuilder();
                                for (int d = 0; d < dimension; d++)
                                {
                                    sb.Append(coordinates[i, d]);
                                    if (d != dimension - 1)
                                        sb.Append(", ");
                                }

                                Console.WriteLine(string.Format("Found a city with index {0} and coordinates ({1})", index, sb.ToString()));
#endif
                            }
                            break;
                        case "DEPOT_SECTION":
                            throw new NotSupportedException();
                        case "EOF":
                            // Do nothing.
                            break;
                        default:
                            throw new ArgumentOutOfRangeException(string.Format("Unkown data encountered. The error occured while parsing TSPLIB data. The following data is not valid: {0}", line));
                    }

                    Console.WriteLine(" done!");
                }

                CalculateDistances();
            }
        }
        #endregion

        #region Properties
        private int dimension;

        /// <summary>
        /// The dimension of the map (eg: 2D, 3D, ...)
        /// </summary>
        public int Dimension
        {
            get { return dimension; }
        }

        private int cityCount;

        /// <summary>
        /// The number of cities on the map
        /// </summary>
        public int CityCount
        {
            get { return cityCount; }
        }

        private string name;
        public string Name
        {
            get { return name; }
        }

        private string comment;
        public string Comment
        {
            get { return comment; }
        }

        private Metric metric;

        /// <summary>
        /// The metric used by this map
        /// </summary>
        public Metric Metric
        {
            get { return metric; }
        }

        private double[,] distances;
        public double GetDistance(int i, int j)
        {
            /*
             * These checks are a little bit overhead --
             * if i or j are out of range, the call to
             * the array will also throw an OutOfRangeException.
             * For the sake of performace, we omit these calls.
             * 
            
            if (i < 0 || i >= cityCount)
                throw new ArgumentOutOfRangeException("i");

            if (j < 0 || j >= cityCount)
                throw new ArgumentOutOfRangeException("j");
             */

            return distances[i, j];
        }

        private double[,] coordinates;
        public double[] GetCoordinates(int city)
        {
            double[] value = new double[dimension];
            for (int i = 0; i < dimension; i++)
                value[i] = coordinates[city, i];

            return value;
        }

        [NonSerialized()]
        private double[] minima;
        public double GetMinimum(int dimension)
        {
            if (minima == null)
                CalculateExtrema();

            return minima[dimension];
        }

        [NonSerialized()]
        private double[] maxima;
        public double GetMaximum(int dimension)
        {
            if (maxima == null)
                CalculateExtrema();

            return maxima[dimension];
        }

        [NonSerialized()]
        private double lowerBound;
        public double LowerBound
        {
            get
            {
                if(lowerBound == 0)
                    CalculateBounds();
                    
                return lowerBound;
            }
        }

        [NonSerialized()]
        private double upperBound;
        public double UpperBound
        {
            get
            {
                if(upperBound == 0)
                    CalculateBounds();
                    
                return upperBound;
            }
        }
        #endregion

        #region Methods
        public double GetCoordinate(int city, int dimension)
        {
            return coordinates[Cyclic.GetIndex(city, CityCount), dimension];
        }

        private void CalculateBounds()
        {
            lowerBound = 0;
            upperBound = 0;

            for (int i = 0; i < cityCount; i++)
            {
                double minimum = double.MaxValue;
                double maximum = double.MinValue;

                for (int j = 0; j < cityCount; j++)
                {
                    // d[i,i] == 0!
                    if (i == j)
                        continue;

                    if (distances[i, j] < minimum)
                        minimum = distances[i, j];

                    if (distances[i, j] > maximum)
                        maximum = distances[i, j];
                }

                lowerBound += minimum;
                upperBound += maximum;
            }
        }

        private void CalculateExtrema()
        {
            minima = new double[dimension];
            maxima = new double[dimension];

            for (int d = 0; d < dimension; d++)
            {
                minima[d] = double.MaxValue;
                maxima[d] = double.MinValue;

                for (int city = 0; city < cityCount; city++)
                {
                    double value = GetCoordinate(city, d);
                    if (value < minima[d])
                        minima[d] = value;

                    if (value > maxima[d])
                        maxima[d] = value;
                }
            }
        }

        public double GetLength(int dimension)
        {
            return Math.Abs(GetMaximum(dimension) - GetMinimum(dimension));
        }

        public double GetOffset(int dimension)
        {
            return GetMinimum(dimension);
        }

        private void CalculateDistances()
        {
            distances = new double[cityCount, cityCount];

            // Calculate the distances for the cities, according to the
            // metric
            for (int i = 0; i < cityCount; i++)
            {
                distances[i, i] = 0;

                for (int j = i + 1; j < cityCount; j++)
                {
                    distances[i, j] = Distance.Calculate(metric, dimension, GetCoordinates(i), GetCoordinates(j));
                    distances[j, i] = distances[i, j];
                }
            }
        }

        private string CleanInputString(string value)
        {
            if (value == null)
                return null;

            string output = value.Trim();
            while (output.IndexOf("  ") >= 0)
                output = output.Replace("  ", " ");

            return output;
        }

        public override string ToString()
        {
            StringBuilder builder = new StringBuilder();

            for (int i = 0; i < this.CityCount; i++)
            {
                for (int j = 0; j < this.CityCount; j++)
                    builder.AppendFormat("{0} ", distances[i, j]);

                builder.AppendLine();
            }

            return builder.ToString();
        }

        #endregion

        #region Static Properties
        public static int DefaultDimension
        {
            get { return 2; }
        }

        public static Metric DefaultMetric
        {
            get { return Metric.Euclidian; }
        }

        public static int DefaultCityCount
        {
            get { return 100; }
        }
        #endregion
    }
}
